#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <assert.h>
#include "include/array_generator.h"
#include "include/array_help.h"

void merge(int arr[], int l, int mid, int r); 

//[l, r]
void sort(int arr[], int l, int r) {
    if (l >= r) return;   // 递归拆分(分治法)，拆到单一元素的时候结束(递归拆分结束条件)

    int mid = l + (r - l) / 2; // 下边界
    sort(arr, l, mid);
    sort(arr, mid + 1, r); 
    merge(arr, l, mid, r);  // 归并，将[l, r] 区间进行排序
}

// TODO 归并结果不正确， 需要修改， 深入学习递归调试技巧，打印递归信息
// 归并
void merge(int arr[], int l, int mid, int r) {
    int dup[r - l + 1];
    CopyArray(dup, arr, l, r); 
    // PrintIntArray(dup, r - l + 1); 
    int i = l, j = mid + 1;  
    for (int k = l; k <= r; k++) { // 归并，相关数组之间，计算偏移量的技巧 ☆☆☆☆☆
        if (l > mid) {
            arr[k] = dup[j - l]; j++; 
        }else if (j > r){
            arr[k] = dup[i - l]; i++;
        }else if (dup[i - l] >= dup[j - l]) {
            arr[k] = dup[j -l ]; j++;
        }else {
            arr[k] = dup[i - l]; i++; 
        }
    }
}


int main(int argc, char *argv[]) {
    int len = 30; 
    int bound = 100;
    int arr[len]; 
    GenRandomArray(arr, len, bound);
    PrintIntArray(arr, len); 
    sort(arr, 0, len - 1); 
    PrintIntArray(arr, len); 
    return 0; 
}